package shape.maze;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;

import shape.maze.Maze.Cell;

public class MazeGenerator {

	int dimX;
	int dimY;

	public MazeGenerator(int dimX, int dimY) {
		this.dimX = dimX;
		this.dimY = dimY;

	}

	public Maze getRandomMaze() {
		boolean[][] maze = new boolean[dimX][dimY];
		for (int i = 0; i < dimX; i++) {
			for (int j = 0; j < dimY; j++) {
				maze[i][j] = false;
			}
		}
		
		ArrayList<Wall> finalWalls = new ArrayList<MazeGenerator.Wall>();
		
		int initX = 0;
		int initY = 0;
		
		maze[initX][initY] = true;

		HashSet<Wall> list = new HashSet<Wall>();
		list.addAll(getCellWalls(new Pair<Integer, Integer>(initX, initY)));
		

		while(!list.isEmpty()){
			Wall selected = getRandomWall(list);
			if(maze[selected.opposite.x][selected.opposite.y]){
				list.remove(selected);
				finalWalls.add(selected);
			}else{
				selected.isPassage = true;
				maze[selected.opposite.x][selected.opposite.y] = true;
				System.out.println("Cell (" + selected.opposite.x + "," + selected.opposite.y+ ") is now part of the maze.");
				list.addAll(getCellWalls(new Pair<Integer, Integer>(selected.opposite.x,selected.opposite.y)));
			}
		}
		
		Cell[][] mazeCells = new Cell[dimX][dimY];
		
		for(int i=0;i<dimX;i++)
			for(int j=0;j<dimY;j++)
				mazeCells[i][j] = new Cell();
		
		for(int i=0;i<dimX;i++){
			mazeCells[i][0].left=true;
			mazeCells[i][dimY-1].right=true;
		}
		
		for(int i=0;i<dimY;i++){
			mazeCells[0][i].down=true;
			mazeCells[dimX-1][i].up=true;
		}
		
		for(Wall w : finalWalls){
			if(!w.isPassage){
				int dx = w.opposite.x - w.init.x;
				int dy = w.opposite.y - w.init.y;
				if(dx > 0 && dy == 0){
					mazeCells[w.init.x][w.init.y].up = true;
				}
				if(dx < 0 && dy == 0){
					mazeCells[w.init.x][w.init.y].down = true;
				}
				if(dx == 0 && dy > 0){
					mazeCells[w.init.x][w.init.y].right = true;
				}
				if(dx == 0 && dy < 0){
					mazeCells[w.init.x][w.init.y].left = true;
				}
			}
		}
		
		mazeCells[initX][initY].down = false;
		mazeCells[dimX-1][dimY-1].right = false;
		
		return new Maze(mazeCells);
	}
	
	private Wall getRandomWall(HashSet<Wall> list){
		Random rnd = new Random();
		Wall selected = null;
		while (selected == null) {
			Iterator<Wall> it = list.iterator();
			while (it.hasNext()) {
				Wall iter = it.next();
				if (rnd.nextGaussian() <= 0) {
					selected = iter;
					break;
				}
			}
		}
		return selected;
	}

	ArrayList<Wall> getCellWalls(Pair<Integer, Integer> init) {
		ArrayList<Wall> ret = new ArrayList<MazeGenerator.Wall>();

		if (init.x > 0)
			ret.add(new Wall(init, new Pair<Integer, Integer>(init.x - 1,
					init.y)));
		if (init.x < dimX - 1)
			ret.add(new Wall(init, new Pair<Integer, Integer>(init.x + 1,
					init.y)));
		if (init.y > 0)
			ret.add(new Wall(init, new Pair<Integer, Integer>(init.x,
					init.y - 1)));
		if (init.y < dimY - 1)
			ret.add(new Wall(init, new Pair<Integer, Integer>(init.x,
					init.y + 1)));

		return ret;
	}

	private class Pair<A, B> {
		public A x;
		public B y;

		public Pair(A x, B y) {
			this.x = x;
			this.y = y;
		}
	}

	private class Wall {
		public boolean isPassage;
		public Pair<Integer, Integer> opposite;
		public Pair<Integer, Integer> init;

		public Wall(Pair<Integer, Integer> init, Pair<Integer, Integer> opposite) {
			this.init = init;
			this.opposite = opposite;
			this.isPassage = false;
		}

		@Override
		public boolean equals(Object obj) {
			boolean ret = false;
			if (obj instanceof Wall) {
				Wall other = (Wall) obj;
				if(opposite.x == other.opposite.x && opposite.y == other.opposite.y){
					if(init.x == other.init.x && init.y == other.init.y){
						ret = true;
					}
				}
				if(opposite.x == other.init.x && opposite.y == other.init.y){
					if(init.x == other.opposite.x && init.y == other.opposite.y){
						ret = true;
					}
				}
			}
			return ret;

		}

		@Override
		public int hashCode() {
			return opposite.x * opposite.y + init.x * init.y;
		}
	}
}
